package algorithm.leetcode.medium;

/*
 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/15
 */
public class Question207 {

    public static void main(String[] args) {
        int[][] prerequisites = {{0, 1}, {1, 2}, {2, 0}};
        Question207 question = new Question207();
        boolean finish = question.canFinish(3, prerequisites);
        System.out.println(finish);
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edgeList = new ArrayList<>(10);
        int[] visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edgeList.add(new ArrayList<>(10));
        }
        for (int[] p : prerequisites) {
            // 要选的课程
            edgeList.get(p[1]).add(p[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (!dfs(edgeList, visit, i)) {
                return false;
            }
        }
        return true;
    }


    private boolean dfs(List<List<Integer>> edgeList, int[] visit, int i) {
        if (visit[i] == 1) {
            return false;
        }
        if (visit[i] == -1) {
            return true;
        }
        visit[i] = 1;
        for (int val : edgeList.get(i)) {
            if (!dfs(edgeList, visit, val)) {
                return false;
            }
        }
        visit[i] = -1;
        return true;
    }
}
